BinarySearchQuestions

Binary Search Problem Set

1. Template Binary Search Problems

These are the classic binary search applications, usually searching directly in arrays or matrices.

  • 704. Binary Search
    Given a sorted array of integers and a target value, return the index if the target is found. If not, return -1.
  • 702. Search in a Sorted Array of Unknown Size
    You are given an array-like data structure with get(index) API but you don’t know the size. Find the target in this sorted structure with minimal calls to get.
  • 74. Search a 2D Matrix
    Write an efficient algorithm to search for a value in a matrix with sorted rows and each row’s first element greater than the last element of the previous row.
  • 240. Search a 2D Matrix II
    Each row and column of the matrix is sorted in ascending order. Search for a target value efficiently.

These problems ask you to find the first occurrence, last occurrence, boundary point, or decision change.

  • 34. Find First and Last Position of Element in Sorted Array
    Given a sorted array of integers, find the starting and ending position of a given target value.
  • 35. Search Insert Position
    Given a sorted array and a target value, return the index if found. If not, return the index where it would be inserted in order.
  • 162. Find Peak Element
    A peak element is one that is strictly greater than its neighbors. Find one peak element’s index using binary search.
  • 278. First Bad Version
    You are given an API isBadVersion(version). Find the first bad version in a sequence of versions (1 to n).
  • 153. Find Minimum in Rotated Sorted Array
    Given a rotated sorted array (no duplicates), find the minimum element.
  • 33. Search in Rotated Sorted Array
    Given a rotated sorted array (no duplicates), search for a target value. Return its index, or -1 if not found.

3. Binary Search on Answer Problems

These are problems where you search for the answer itself (min/max value) instead of searching directly in the array. You define the feasible range and use binary search to test.

  • 69. Sqrt(x)
    Given a non-negative integer x, compute and return the square root of x, rounded down to the nearest integer.
  • 875. Koko Eating Bananas
    Koko loves to eat bananas. There are n piles of bananas, each pile has piles[i] bananas. The guards will come back in h hours. Find the minimum integer eating speed k such that she can eat all bananas before the guards return.